using System;
using System.Runtime.CompilerServices;

namespace HTCollections.Custom
{
    /// <summary>
    /// 优先级队列
    /// </summary>
    public sealed class PriorityQueue<T>
    {
        public PriorityItem[] Data;
        public int Capacity;
        public int Length;

        /// <summary>
        /// 是否为降序排列（大顶堆）
        /// </summary>
        public bool IsDescending;

        /// <summary>
        /// 优先级队列
        /// </summary>
        /// <param name="isDescending">是否为降序排列（大顶堆）</param>
        public PriorityQueue(bool isDescending = false)
        {
            IsDescending = isDescending;
            Capacity = 4;
            Data = new PriorityItem[Capacity];
            Length = 0;
        }

        /// <summary>
        /// 优先级队列
        /// </summary>
        /// <param name="capacity">初始容量</param>
        /// <param name="isDescending">是否为降序排列（大顶堆）</param>
        public PriorityQueue(int capacity, bool isDescending = false)
        {
            IsDescending = isDescending;
            Capacity = capacity;
            Data = new PriorityItem[Capacity];
            Length = 0;
        }

        public PriorityQueue(PriorityQueue<T> priorityQueue)
        {
            IsDescending = priorityQueue.IsDescending;
            Capacity = priorityQueue.Capacity;
            Data = new PriorityItem[Capacity];
            Length = priorityQueue.Length;
            Array.Copy(priorityQueue.Data, 0, Data, 0, Length);
        }

        public PriorityItem this[int index]
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get
            {
                CollectionsUtil.CheckIndexInRange(index, Length);
                return Data[index];
            }
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            set
            {
                CollectionsUtil.CheckIndexInRange(index, Length);
                Data[index] = value;
            }
        }

        public void Enqueue(T value, int priority)
        {
            Add(value, priority);
            if (IsDescending)
                Enqueue_Descending(); //大顶堆
            else
                Enqueue_Ascending(); //小顶堆
        }

        public T Dequeue()
        {
            if (Length == 1)
            {
                T ret = Data[0].Value;
                Clear();
                return ret;
            }
            else
            {
                int lastIndex = Length - 1;
                Swap(0, lastIndex); //交换首尾元素
                T ret = Data[lastIndex].Value;
                RemoveAt(lastIndex); //移除尾
                if (IsDescending)
                    UpdateHeap_Descending(0, lastIndex); //调整堆(大顶堆)
                else
                    UpdateHeap_Ascending(0, lastIndex); //调整堆(小顶堆)
                return ret;
            }
        }

        public T Peek()
        {
            return Data[0].Value;
        }

        public void Clear()
        {
            if (Length == 0) return;
            Array.Clear(Data, 0, Length);
            Length = 0;
        }


        /// <summary>
        /// 大顶堆
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void Enqueue_Descending()
        {
            int index = Length - 1;
            while (index > 0)
            {
                int index2 = (index - 1) / 2;
                var a = Data[index];
                var b = Data[index2];
                if (a.Priority < b.Priority) break; //子节点 >= 父节点
                Data[index] = b; //交换父子节点
                Data[index2] = a;
                index = index2; //更新 index
            }
        }

        /// <summary>
        /// 小顶堆
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void Enqueue_Ascending()
        {
            int index = Length - 1;
            while (index > 0)
            {
                int index2 = (index - 1) / 2;
                var a = Data[index];
                var b = Data[index2];
                if (a.Priority >= b.Priority) break; //子节点 < 父节点
                Data[index] = b; //交换父子节点
                Data[index2] = a;
                index = index2; //更新 index
            }
        }

        /// <summary>
        /// 调整（大顶）堆，Priority 值最大的在堆顶
        /// </summary>
        /// <param name="i">待调整的数据的索引</param>
        /// <param name="len">数据列表长度</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void UpdateHeap_Descending(int i, int len)
        {
            var temp = Data[i]; //记录待 调整 的值
            for (int k = 2 * i + 1; k < len; k = 2 * k + 1)
            {
                if (k + 1 < len) //存在右节点
                {
                    if (Data[k + 1].Priority >= Data[k].Priority) //右节点 >= 左节点
                    {
                        k += 1; //选择较大的右节点
                    }
                }

                //（左/右）子节点 >= 父节点
                if (Data[k].Priority >= temp.Priority)
                {
                    Swap(k, i); //交换（要保证父节点一定大于子节点——大顶堆）
                    i = k; //更新 i ，继续下一次循环
                }
                //子节点<父节点
                else
                {
                    break; //跳出循环，此处不需要往深层次遍历的原因在于：在堆排序中是从最后一个非叶子节点开始倒着向前 UpdateHeap
                }
            }
        }

        /// <summary>
        /// 调整（小顶）堆，Priority 值最小的在堆顶
        /// </summary>
        /// <param name="i">待调整的数据的索引</param>
        /// <param name="len">数据列表长度</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void UpdateHeap_Ascending(int i, int len)
        {
            var temp = Data[i]; //记录待 调整 的值
            for (int k = 2 * i + 1; k < len; k = 2 * k + 1)
            {
                if (k + 1 < len) //存在右节点
                {
                    if (Data[k + 1].Priority < Data[k].Priority) //右节点 < 左节点
                    {
                        k += 1; //选择较小的右节点
                    }
                }

                //（左/右）子节点 < 父节点
                if (Data[k].Priority < temp.Priority)
                {
                    Swap(k, i); //交换（要保证父节点一定小于子节点——小顶堆）
                    i = k; //更新 i ，继续下一次循环
                }
                //子节点>父节点
                else
                {
                    break; //跳出循环，此处不需要往深层次遍历的原因在于：在堆排序中是从最后一个非叶子节点开始倒着向前 UpdateHeap
                }
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        void Swap(int a, int b)
        {
            var temp = Data[a];
            Data[a] = Data[b];
            Data[b] = temp;
        }

        /// <summary>
        /// 添加元素
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        int Add(T value, int priority)
        {
            int index = Length;
            if (Length == Capacity)
                ArrayUtil.Resize(ref Data, Capacity = ArrayUtil.GetCapacity(Capacity));
            PriorityItem item = new PriorityItem()
            {
                Value = value,
                Priority = priority,
            };
            Data[index] = item;
            Length++;
            return index;
        }

        /// <summary>
        /// 删除指定索引元素
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        bool RemoveAt(int index)
        {
            if (index < 0 || index >= Length) return false;
            Length--;
            Array.Copy(Data, index + 1, Data, index, Length - index);
            Data[Length] = default;
            return true;
        }

        public struct PriorityItem
        {
            public T Value;
            public int Priority;
        }
    }
}